class Matrice:


    def __init__(self, ligne, col):
        self.l = ligne
        self.col = col
        self.mat = []
        for l in range(0, ligne):
            self.mat.append(list())
            for c in range(0, col):
                self.mat[l].append(" ");
        
        

    def ligne(self):
        res = ""
        for i in range(0,self.col*4+1):
            res+="-"
        return res
    
    def printMat(self):
        s = ""
        for l in range(0, self.l):
            self.mat.append(list())
            for c in range(0, self.col):
                s += "| "+str(self.mat[l][c])+" ";
            print "%s|" %s
            print self.ligne()
            s = ""
            
    def insert(self, ligne, col, lettre):
        self.mat[ligne][col] = lettre
        
    def find(self, ligne, col, lettre):
        trouve = False
        listCoord = list()
        "haut"
        if ligne - 1 >= 0:
            trouve = self.mat[ligne - 1][col] == lettre
            if(trouve):
                listCoord.append([ligne-1,col])
        "bas"
        if ligne + 1 < self.l:
            trouve = self.mat[ligne + 1][col] == lettre
            if(trouve):
                listCoord.append([ligne+1,col])
        "gauche"
        if col - 1 >= 0:
            trouve =  self.mat[ligne][col - 1] == lettre
            if(trouve):
                listCoord.append([ligne,col-1])
        
        "droite"
        if col + 1 < self.col:
            trouve = self.mat[ligne][col + 1] == lettre
            if(trouve):
                listCoord.append([ligne,col+1])
        return listCoord
    
    def setMot(self, mot):
        nbLigne = int(len(mot)/self.col)
        l = int(self.l / 2) - int(nbLigne/2)
        ind = 0
        add=True
        
        for lettre in mot:
            if(ind < self.col and add or not add and ind >= 0):
                self.mat[l][ind] = lettre
                if(add):
                    ind += 1
                else :
                    ind -= 1
            else :
                l += 1
                if add:
                    ind -=1
                else : 
                    ind += 1
                self.mat[l][ind] = lettre
                if add:
                    ind -=1
                else : 
                    ind += 1
                add = not add
                
    def findWord(self,ligne,col,mot):
        stack = list()
        if self.mat[ligne][col] == mot[0] :
            stack.append([ligne,col]) 
            return self.findRecursif(stack, mot[1:len(mot)])
        else : 
            return False
                
                
    def findRecursif(self,stack, mot):
        if mot == "" :
            return True
        top = stack[len(stack)-1]
        for case in self.find(top[0], top[1], mot[0]) : 
            contains = False
            for oldCase in stack : 
                if (case[0] == oldCase[0] and  case[1] == oldCase[1]):
                    contains = True
            if not contains :
                stack.append([case[0], case[1]])
                if self.findRecursif(stack,mot[1:len(mot)]) : 
                    return True
                else : 
                    stack.pop()
        return False
    
    def joue(self, ligne, col, lettre, mot):
        if lettre != mot[0] :
            return False
        self.mat[ligne][col] = lettre
        return self.findWord(ligne, col, mot)
    